package sort

import (
	"math"
	"traning/algorithm/utility"
)

// 年龄的排序示例
func CountSortByAges(arr []int) {
	help := make([]int, 200)
	for _, v := range arr {
		help[v]++
	}
	index := 0
	for i, v := range help {
		for v > 0 {
			arr[index] = i
			index++
			v--
		}
	}
}

// 适用于非负的数组排序
func CountSort(arr []int){
	if len(arr) < 2 {
		return
	}
	var max int = math.MinInt64
	for _, n := range arr {
		max = utility.Max(max, n)
	}
	var buckets []int = make([]int, max+1)
	for _, n := range arr {
		buckets[n]++
	}
	var index int
	for value, count := range buckets {
		for count > 0 {
			arr[index] = value
			index++
			count--
		}
	}
}